# -*- coding: utf-8 -*-

"""剑指 Offer II 081. 允许重复选择元素的组合
给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：
输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

示例 4：
输入: candidates = [1], target = 1
输出: [[1]]

示例 5：
输入: candidates = [1], target = 2
输出: [[1,1]]

提示：
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500"""


class Solution:
    """本质上还是排列组合，回溯，递归
    如果选择当前元素，下一回还是决策该元素；如果不选择当前元素，下一回决策下一个元素
    终止条件：
    1.如果已经收集的组合数目达到150，停止（剪枝）
    2.total>target, 停止 （剪枝）
    3.total==target, 收集+停止
    4.元素用完，停止

    提交通过，看题解，要提高效率，在大方向都是回溯递归的情况下，就看怎么剪枝。
        其中有种方案，先将 candidates 进行排序，如果后续的元素都大于缺口值的时候，停止
    """
    def combinationSum(self, candidates, target: int):
        answer, hi = [], len(candidates)
        def fork(i, group, total):
            if len(answer) >= 150:
                return
            
            if total > target:
                return
            
            if total == target:
                answer.append(group)
                return
            
            if i == hi:
                return
            
            group_new = group.copy()
            group_new.append(candidates[i])
            
            fork(i, group_new, total+candidates[i])
            fork(i+1, group, total)
        
        fork(0, [], 0)
        return answer


if __name__ == '__main__':
    so = Solution()
    print(so.combinationSum(candidates = [2,3,6,7], target = 7))
    print(so.combinationSum(candidates = [2,3,5], target = 8))
    print(so.combinationSum(candidates = [2], target = 1))
    print(so.combinationSum(candidates = [1], target = 1))
    print(so.combinationSum(candidates = [1], target = 2))
